#include <iostream>
using namespace std;
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution 
{
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            ListNode * l = new ListNode(0);
            ListNode * ltemp = l;
            ListNode * last = l;
            while( l1 != NULL || l2 != NULL)
            {
                l->next = new ListNode(0);
                if ( l1 && l2)
                {
                    l->val +=  l1->val + l2->val;
                    l1 = l1->next;
                    l2 = l2->next;
                }
                else if (l1)
                {
                    l->val += l1->val;
                    l1 = l1->next;
                }
                else if (l2)
                {
                    l->val += l2->val;
                    l2 = l2->next;
                }
                if (l->val >= 10)
                {
                    l->next->val += 1;
                    l->val -= 10;
                }
                last = l;
                l = l->next;

            }
            if (last->next->val == 0)
                last->next = NULL;
            return ltemp;
        }
};

int main()
{
    ListNode * l1, *l2;
    #if 0
    l1 = new ListNode(0);
    l1->val = 2;
    l1->next = new ListNode(0);
    l1->next->val = 4;
    l1->next->next = new ListNode(0);
    l1->next->next->val = 3;
    l1->next->next->next = NULL;

    l2 = new ListNode(0);
    l2->val = 5;
    l2->next = new ListNode(0);
    l2->next->val = 6;
    l2->next->next = new ListNode(0);
    l2->next->next->val = 4;
    l2->next->next->next = NULL;
    #endif

    l1 = new ListNode(0);
    l2 = new ListNode(0);
    l1->val = 5;
    l2->val = 5;
    Solution s;
    ListNode * l = s.addTwoNumbers(l1, l2);
    while(l)
    {
        cout << l->val << endl;
        l = l->next;
    }
    return 0;
}
